
//1475.商品折扣后的最终价格
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        //从右往左,记录下一个可能满足条件的位置
        int n=prices.size();
        stack<pair<int,int>> st;
        st.push({prices[n-1],n-1});

        vector<int> ret(prices);
        for(int i=n-2;i>=0;i--)
        {
            while(!st.empty()&&st.top().first>prices[i])  //在栈里面找满足条件的
                st.pop();

            if(st.empty()) ret[i]=prices[i];  //栈为空,没有满足条件的
            else ret[i]=prices[i]-st.top().first;  //栈不为空,栈顶为第一个满足条件的

            st.push({prices[i],i});
        }        
        return ret;
    }
};